剑指 Offer 56 - I. 数组中数字出现的次数
一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

https://leetcode.cn/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/description/?favorite=xb9nqhhg


hash map

int* singleNumbers(int* nums, int numsSize, int* returnSize)
{
    *returnSize=2;
    int*ans=(int*)malloc(sizeof(int)*2);
    int tmp[10001]={0};
    int count=0;

    int max=0;
    int min=0;
    for(int i=0;i<numsSize;i++)
    {
        if(nums[i]>max)
        {
            max=nums[i];
        }
        if(nums[i]<min)
        {
            min=nums[i];
        }
    }
    for(int i=0;i<numsSize;i++)
    {
        tmp[nums[i]-min]+=1;
    }

    for(int i=0;i<max-min+1;i++)
    {
        if(tmp[i]==1)
        {
            ans[count]=i+min;
            count++;
        }
    }
    return ans;
}




分组异或
int* singleNumbers(int* nums, int numsSize, int* returnSize)
{
    int pos=0;
    int tmp=0;
    int* ans=(int*)malloc(sizeof(int)*2);
    for(int i=0;i<numsSize;i++)
    {
        tmp^=nums[i];
    }
    //记录第一个不同的位
    for(int i=0;i<32;i++)
    {
        if((tmp>>i)&1==1)
        {
            pos=i;
            break;
        }
    }

    //按照记录的位数分组
    int nums1=0;
    int nums2=0;
    for(int i=0;i<numsSize;i++)
    {
        if((nums[i] >> pos) & 1 == 1)
        {
            nums1 ^= nums[i];
        }
        else     
        {
            nums2 ^= nums[i];
        }

     
    }
    ans[0]=nums1;
    ans[1]=nums2;
    *returnSize=2;
    return ans;
}